#include <iostream>
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

ListNode *reverseKGroup(ListNode *head, int k) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(!head)
		return NULL;

	ListNode *pDummy = new ListNode(0);
	pDummy->next = head;

	ListNode *ppsHead = pDummy;
	ListNode *psHead = head;
	int count;
	while(1){
		count = 0;
		ListNode *pCur = ppsHead;
		// find section end
		while(pCur->next && count<k){
			++count;
			pCur = pCur->next;
		}
		if(count<k){
			break;
		}
		// pCur point to section end
		ListNode *psEnd = pCur;
		ListNode *pPre = ppsHead;
		pCur = psHead;
		while(pPre!=psEnd){
			ListNode *pNext = pCur->next;
			pCur->next = pPre;
			pPre = pCur;
			pCur = pNext;
		}
		// pCur point to next of psEnd, pPre point to psEnd
		psHead->next = pCur;
		ppsHead->next = pPre;
		// begin a new section
		ppsHead = psHead;
		psHead = pCur;
	}
	ListNode *pRes = pDummy->next;
	delete pDummy;
	return pRes;
}


int main(){
	ListNode node(1);
	reverseKGroup(&node,1);
	return 0;
}